package com.Earth01;

import java.util.*;

/*
* 448. 找到所有数组中消失的数字
* */
public class Earth240712 {
    public static void main(String[] args) {
        int[] nums = {1,1};
        List<Integer> res = findDisappearedNumbers3(nums);
        System.out.println(res);
    }
    public static List<Integer> findDisappearedNumbers1(int[] nums) {
        /*
        * 思路1：哈希Set，空间复杂度爆炸
        * */
        List<Integer> list = new ArrayList<>();
        Set<Integer> hashset = new HashSet<>();
        //将1~8添加给list，数组内容添加给hashset
        for (int i = 0; i < nums.length; i++) {
            //list.add(i+1);
            hashset.add(nums[i]);
        }
        for (int i = 1; i <= nums.length; i++) {
            if(!hashset.contains(i)){
                list.add(i);
            }
        }
        return list;
    }

    public static List<Integer> findDisappearedNumbers2(int[] nums) {
        /*
         * 思路2：在nums数组中，空间复杂度为1
         *   遍历数组nums,每拿到一个值value，就将其nums[value-1]的值加上n
         *   遍历前需要%n，以便保持数组值不变。因为所有数组所有元素都在[1,n]之间，不存在越界问题
         *   遍历结束后，哪个位置的值小于n，[1,n]哪个值就没出现过
         * */
        List<Integer> list = new ArrayList<>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int x = (nums[i] - 1) % length;//一定在[1,length]之间
            nums[x] += length;//将出现在[1,length]之间
        }
        for (int i = 0; i < length; i++) {
            if(nums[i] <= length){
                list.add(i+1);
            }
        }
        return list;
    }

    public static List<Integer> findDisappearedNumbers3(int[] nums) {
        /*
            思路3：使用arr数组，空间复杂度为n
            设置一个arr数组，数组的内容全为1。遍历nums数组，每拿到一个nums数组的元素，就在arr数组对应的位置+n。
            nums数组结束后，arr数组中<=n的元素便为：在 [1, n] 范围内但没有出现在 nums 中的数字
         */
        List<Integer> list = new ArrayList<>();
        int length = nums.length;
        int[] arr = new int[length];
        Arrays.fill(arr,1);
        for (int i = 0; i < length; i++) {
            int index = nums[i] - 1;
            arr[index] += length;//将出现在[1,length]之间
        }
        for (int i = 0; i < length; i++) {
            if(arr[i] <= length){
                list.add(i+1);
            }
        }
        return list;
    }
}
